#pragma once
#include "Disk.h"
#include <list>

class CSortTests
{
public:
	CSortTests(void);

	~CSortTests(void);


	void SortingUnitTest(int nRel1RowsNum, int nRel2RowsNum, int nRel1ByteCount, int nRel2ByteCount, wstring wsRel1FileNameFlash,
								 wstring wsRel2FileNameFlash);

	template <class T>
	bool SortInIterations(int nCurrIteration, int nTotalNumOfIterations, wstring wsRelFileName, wstring wsSortedFileName, int nRelRowsNum,
							int nRelByteCount, float& rfTimeSec, float* pfIoTimeMsec, int& rnReadSectorsNum, int& rnWrittenSectorsNum, wstring& rwsFinalFileName, wstring &rwsAppend);

//	void SortingUnitTest();

	template <class T>
	bool SortInBlocks(wstring wsRelFileName, wstring wsSortedFileName, int nRelRowsNum,
						int nRelByteCount, float& rfTimeSec,  float* pfIoTimeMsec, int& rnReadSectorsNum, int& rnWrittenSectorsNum, wstring wsAppend);

	template <class T>
	bool SortInBlocksV1(wstring wsRelFileName, wstring wsSortedFileName, int nRelRowsNum,
						int nRelByteCount, float& rfTimeSec,  float* pfIoTimeMsec, int& rnReadSectorsNum, 
						int& rnWrittenSectorsNum, wstring wsAppend, double fReadBufferRatio);


	template <class T>
	bool MergeSortKs(wstring wsRelFileName, wstring wsSortedFileName, int nRelRowsNum,
						int nRelByteCount, float& rfTimeSec, int& rnReadSectorsNum, int& rnWrittenSectorsNum);


	template <class T>
	bool MergeSortKsV1(wstring wsRelFileName, wstring wsSortedFileName, int nRelRowsNum,
						int nRelByteCount, float& rfTimeSec, int& rnReadSectorsNum, int& rnWrittenSectorsNum);

	template <class T>
	bool MergeSortKsV2(wstring wsRelFileName, wstring wsSortedFileName, int nRelRowsNum,
						int nRelByteCount, float& rfTimeSec, float* pfIoTimeMsec, int& rnReadSectorsNum, int& rnWrittenSectorsNum);

	template <class T>
	bool MergeSortKsV3(wstring wsRelFileName, wstring wsSortedFileName, int nRelRowsNum,
						int nRelByteCount, float& rfTimeSec, float* pfIoTimeMsec, int& rnReadSectorsNum, int& rnWrittenSectorsNum,
						double fReadBufferRatio, bool bUseQuickSort = true);

	// don't use it - with 3 buffers
	template <class T>
	bool MergeSortKsV4(wstring wsRelFileName, wstring wsSortedFileName, int nRelRowsNum,
						int nRelByteCount, float& rfTimeSec, float* pfIoTimeMsec, int& rnReadSectorsNum, int& rnWrittenSectorsNum,
						double fReadBufferRatio);

	// don't use it - with erase units writing blocks
	template <class T>
	bool MergeSortKsV5(wstring wsRelFileName, wstring wsSortedFileName, int nRelRowsNum,
						int nRelByteCount, float& rfTimeSec, float* pfIoTimeMsec, int& rnReadSectorsNum, int& rnWrittenSectorsNum,
						double fReadBufferRatio);

	template <class T>
	bool AlmostSortedMerge(wstring wsRelFileName, wstring wsSortedFileName, int nRelRowsNum,
						int nRelByteCount, float& rfTimeSec,  float* pfIoTimeMsec, int& rnReadSectorsNum, int& rnWrittenSectorsNum);


	template <class T>
	bool PiecewiseSortedMerge(wstring wsRelFileName, wstring wsSortedFileName, int nRelRowsNum,
						int nRelByteCount, float& rfTimeSec,  float* pfIoTimeMsec, int& rnReadSectorsNum, int& rnWrittenSectorsNum);


	template <class T>
	void QuickSort(T arr[], int nBegInd, int nEndInd);

	template <class T>
	void QuickSort1(T arr[], int nBegInd, int nEndInd);

	template <class T>
	void QuickSort2(T arr[], int left, int right, bool bIsFirstPivot = true);


	void SetBufferLimitedByteCount(int nBufferLimitedByteCount);

	void Test(ostream& fResults, int nIteration, int nRel1RowsNum, int nRel2RowsNum, int nRel1ByteCount, int nRel2ByteCount,
				int nSmallRelByteCount, int nBigRelByteCount, wstring wsRel2FileName, wstring wAppend);

	void Test1(ostream& fResults, int nIteration, int nRel1RowsNum, int nRel2RowsNum, int nRel1ByteCount, int nRel2ByteCount,
				int nSmallRelByteCount, int nBigRelByteCount, wstring wsRel2FileName);

	template <class T>
	bool CreateBlockSortedRelation( wstring wsRelFileName, wstring wsSortedFileName, wstring wsRsFileName, int nRelRowsNum,
											int nRelByteCount, float& rfTimeSec, float* pfIoTimseMsec, int& rnReadSectorsNum, int& rnWrittenSectorsNum, 
											bool bUseRs);

	template <class T>
	bool RadixSortV1(wstring wsRelFileName, wstring wsSortedFileName, int nRelRowsNum, float fColumDensity,
						int nRelByteCount, float& rfTimeSec, int& rnReadSectorsNum, int& rnWrittenSectorsNum);

	template <class T>
	bool RadixSortV2(wstring wsRelFileName, wstring wsSortedFileName, int nRelRowsNum, float fColumDensity,
						int nRelByteCount, float& rfTimeSec, float* pfIoTimeMsec, int& rnReadSectorsNum, int& rnWrittenSectorsNum, wstring wsAppend);

	template <class T>
	int Merge2SortedArrays(T* pBuffer, int nNumOfElems1, int nNumOfElems2, int nMaxSize);

	
	bool PiecesUnitTests(int nRel2ByteCount);

	template <class T>
	bool FindSortedBlocks(wstring wsRelFileName, int nRelRowsNum, int nRelByteCount, float& rfTimeSec,  
							float* pfIoTimeMsec, int& rnReadSectorsNum, int& rnWrittenSectorsNum, SSortedPieceInfo** pPartsInfo,
							int& rnNumberOfSortedBlocks);

	void SortingUnitTest1(int nRel1RowsNum, int nRel2RowsNum, int nRel1ByteCount, int nRel2ByteCount, wstring wsRel1FileNameFlash,
								 wstring wsRel2FileNameFlash);

	void Merge2SortedArraysTest(int nRowsNum);



private:

	bool AllocateVirtualBuffer(void** pBuffer, int nBytesCount);

	bool DeAllocateVirtualBuffer(void** pBuffer, int nBytesCount);

	template <class T>
	bool InsertToResultList(T* pNewElem, list<T>* pSmallersList);

	void PrintResults(ostream& fResults, float fTimeSec, int nReadSectorsNum);
	void PrintResults(ostream& fResults, float fTimeMsec, float fIoTimeMsec, int nReadSectorsNum, int nWrittenSectorsNum);


	float CalcTime(DWORD dwStart, DWORD dwStop);

	float CalcTime(LARGE_INTEGER startTime, LARGE_INTEGER endTime);




	SRel1* m_psRel1Buffer;
	SRel2* m_psRel2Buffer;

	// Intermediate members for function: MergeSortKs
	int m_nMaxElemInList;
	int n_nLastBufferElems;
	int m_nMaxElemMul;

	int m_nBufferLimitedByteCount;

	unsigned __int64	m_adwStart[1000];
	unsigned __int64	m_adwEnd[1000];
	int		m_nTimeIndex;

	LARGE_INTEGER  m_freq;
};


template <class T>
void CSortTests::QuickSort(T arr[], int nBegInd, int nEndInd)
{

  /////////////////////////////////////
  // Partition
  if (nEndInd > nBegInd + 1)
  {
    T* piv			= &(arr[nBegInd]);
	int nleftInd	= nBegInd + 1;
	int nRightInd	= nEndInd;

    while (nleftInd < nRightInd)
    {
      if (arr[nleftInd] <= *piv)
        nleftInd++;
      else
	  {
		// Swap
		T temp			= arr[nleftInd];
		arr[nleftInd]	= arr[--nRightInd];
		arr[nRightInd]	= temp;
	  }
    }

	// Swap
	T temp			= arr[--nleftInd];
	arr[nleftInd]	= arr[nBegInd];
	arr[nBegInd]	= temp;
	//
	////////////////////////////////////////

    QuickSort(arr, nBegInd, nleftInd);
    QuickSort(arr, nRightInd, nEndInd);
  }
}


// Sort the elements of a between indexes left and right inclusive
// In this implementation the pivot is the maximum
 template <class T>
 void CSortTests::QuickSort1(T arr[], int nBegInd, int nEndInd) 
 {
	 if (nEndInd <= nBegInd) return;

	 int newPivotIdx = 0;

	 while (nEndInd > nBegInd) 
	 {
		  /////////////////////////////////////
		  // Partition

		 	int nUp		= nBegInd;
			int nDown	= nEndInd;
			T* part		= &(arr[nEndInd]);

			if (nEndInd <= nBegInd)	
			{
				newPivotIdx = nBegInd;
			}
			else
			{
				while(true)
				{
					while ((arr[nUp] < *part)/*&& (nUp<nDown)*/)
					{
						nUp++;
					}

					while ((*part < arr[nDown]) && (nUp<nDown))
					{
						nDown--;
					}

					if (nUp >= nDown)
					{
						break;
					}

					// Swap
					T temp			= arr[nUp];
					arr[nUp]		= arr[nDown];
					arr[nDown]		= temp;

					nUp++;
					nDown--;

				}
				// Swap
				T temp			= arr[nUp];
				arr[nUp]		= arr[nEndInd];
				arr[nEndInd]	= temp;

				
			}
			newPivotIdx = nUp;
//			printf("newPivotIdx = %d \n", nUp);

			if (newPivotIdx - nBegInd > nEndInd - newPivotIdx) 
			{
				QuickSort1(arr, newPivotIdx+1, nEndInd);
				nEndInd = newPivotIdx - 1;
			} 
			else 
			{
				QuickSort1(arr, nBegInd, newPivotIdx-1);
				nBegInd = newPivotIdx + 1;
			}
	 }
 }


// Sort the elements of a between indexes left and right inclusive
// In this implementation the pivot is the middle

 template <class T>
 void CSortTests::QuickSort2(T arr[], int left, int right, bool bIsFirstPivot /*= true*/) {
      int i = left, j = right;
      T tmp;

	  T pivot;

	  if (true == bIsFirstPivot)
	  {
		// pivot = first element
		pivot = arr[left];
	  }
	  else
	  {
		// pivot = middle element
//		pivot = arr[left + ((right - left)/2)];
		pivot = arr[left + static_cast<int>(floor((right - left)/2.0))];

		 //pivot = (arr[static_cast<int>(floor((left + right) / 2.0f))]);
	  }

      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };
 
      /* recursion */
      if (left < j)
            QuickSort2(arr, left, j, bIsFirstPivot);
      if (i < right)
            QuickSort2(arr, i, right, bIsFirstPivot);
}

template <class T>
bool CSortTests::CreateBlockSortedRelation( wstring wsRelFileName, wstring wsSortedFileName, wstring wsRsFileName, int nRelRowsNum,
											int nRelByteCount, float& rfTimeSec, float* pfIoTimseMsec, int& rnReadSectorsNum, int& rnWrittenSectorsNum, 
											bool bUseRs)
{
	// TODO: don't need so many buffers - only one
	bool bRes					= false;
	T* psRelBuffer				= NULL;
	T* psRelSoretdBuffer		= NULL;


	if (false == AllocateVirtualBuffer((void**)(&psRelBuffer), m_nBufferLimitedByteCount ))
	{
		return false;
	}

	Disk* psDiskRel			= new Disk(wsRelFileName, eLogical, eRead);
	Disk* psDiskSortedRel	= new Disk(wsSortedFileName, eLogical, eWrite);

	int nNumOfLinesInBlock	= (m_nBufferLimitedByteCount / sizeof(T));
	int nNumOfIterations	= static_cast<int>(ceil(static_cast<float>(nRelByteCount) / m_nBufferLimitedByteCount));

	if (psDiskRel->OpenDisk() && psDiskSortedRel->OpenDisk())
	{
		if (psDiskRel->CreateOverlappedEvent() && psDiskSortedRel->CreateOverlappedEvent())
		{		

			DWORDLONG dwlOffset = 0;

			LARGE_INTEGER  startTime;
			QueryPerformanceCounter((LARGE_INTEGER *)&startTime);


			for (int j = 0; j < nNumOfIterations; ++j)
			{
				dwlOffset = (j * m_nBufferLimitedByteCount);
				// TODO: add a case when the offset is not sector aligned
				// Read a block of the relation
				if (psDiskRel->DoOverlappedIO(psRelBuffer, m_nBufferLimitedByteCount, dwlOffset, &rnReadSectorsNum, pfIoTimseMsec))
				{
					//DWORD dwStart1 = timeGetTime();

					//QuickSort1(psRelBuffer, 0, nNumOfLinesInBlock-1);
					//QuickSort(psRelBuffer, 0, nNumOfLinesInBlock);
					QuickSort2(psRelBuffer, 0, nNumOfLinesInBlock-1);

					//DWORD dwEnd1 = timeGetTime();
					//float fTimeMsec = CalcTime(dwStart1, dwEnd1);
//					printf("Time to quick-sort = %f [msec]\n",fTimeMsec);

					// Write the sorted buffer into the disk
					if (psDiskSortedRel->DoOverlappedIO(psRelBuffer, m_nBufferLimitedByteCount, dwlOffset, &rnWrittenSectorsNum, pfIoTimseMsec))
					{
						bRes = true;						
					}
					else
					{
						bRes = false;
					}
				}
			}

			//DWORD dwStop = timeGetTime();
			LARGE_INTEGER  endTime;
			QueryPerformanceCounter((LARGE_INTEGER *)&endTime);
			rfTimeSec += CalcTime(startTime, endTime);


			//rfTimeSec += CalcTime(dwStart, dwStop);

			psDiskRel->CloseDisk();
			psDiskSortedRel->CloseDisk();
		}
	}

	DeAllocateVirtualBuffer((void**)(&psRelBuffer), m_nBufferLimitedByteCount);

	delete psDiskRel;
	delete psDiskSortedRel;

	return bRes;
}

